public class Hash {
    public class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key, int val){
            this.key = key;
            this.val = val;
        }

    }
    public Node[] array;
    public int usedSize;
    public Hash(){
        array = new Node[10];
        usedSize = 10;
    }


    public void put(int key, int val){
        Node node = new Node(key, val);
        int index = key % usedSize;
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                cur.val = node.val;
                return;
            }
            cur = cur.next;
        }
        //头插
        cur.next = array[index];
        array[index] = cur;
        usedSize++;
    }
    private void grow(){
        Node[] newArray = new Node[array.length * 2];
        //1.遍历每个元素的链表
        //2.每遍历到一个结点都要重新哈希
        //3.进行头插
        for(int i = 0; i < array.length; i++){
            Node cur = array[i];
            while(cur.next != null){
                int index = cur.key % newArray.length;
                Node curNext = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
        this.usedSize = newArray.length;
    }


}
